//
// Created by francklinson on 2021/5/16.
//
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char>> &matrix) {
        if (matrix.empty()) return 0;
        int row = static_cast<int>(matrix.size());
        int col = static_cast<int>(matrix[0].size());
        vector<vector<int>> prefix(row, vector<int>(col, 0));
        int ans = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '0') prefix[i][j] = 0;
                else {
                    if (i > 0) prefix[i][j] = prefix[i-1][j] + 1;
                    else prefix[i][j] = 1;
                }
            }
            ans = max(ans, largestRectangleArea(prefix[i])); // 这一行的最大矩形
        }
        return  ans ;
    }
    int largestRectangleArea(vector<int> &heights) { // 单调栈 + 常数优化  84题功能
        int n = (int)heights.size();
        vector<int> left(n, -1), right(n, n);
        stack<int> mono;
        for (int i = 0; i < n; ++i) {
            while (!mono.empty() and heights[i] <= heights[mono.top()]) {
                right[mono.top()] = i;
                mono.pop();
            }
            left[i] = (mono.empty() ? -1 : mono.top());
            mono.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;

    }
};

int main() {
    vector<vector<char>> matrix{{'1', '0', '1', '0', '0'},
                                {'1', '0', '1', '1', '1'},
                                {'1', '1', '1', '1', '1'},
                                {'1', '0', '0', '1', '0'}};
    Solution sol;
    cout << sol.maximalRectangle(matrix) << endl;
    return 0;
}